home *** CD-ROM | disk | FTP | other *** search
/ Amiga Games 1996 July / Amiga Games 1996 #7.iso / archive / userbox / publicdomain / hildu.lha / HiL-Du / hilsort.asm < prev    next >
Assembly Source File  |  1996-03-27  |  4KB  |  168 lines
  1.  
  2.  
  3.         INCLUDE 'exec/types.i'
  4.         INCLUDE 'macros.i'
  5.  
  6.         INCLUDE 'exec/memory.i'
  7.  
  8.         INCLUDE 'utility/hooks.i'
  9.  
  10.         INCLUDE 'lvo/exec_lib.i'
  11.  
  12.         SECTION code,CODE
  13.  
  14.         NEAR    A4
  15.  
  16.         XREF    _SysBase
  17.  
  18. ;***** #c
  19. ;***** =hil.lib
  20.  
  21. ;***** QSort
  22. ;* =    performs a quicksort operation.
  23. ;* i    array, A0, APTR * = Array to be sorted
  24. ;* i    items, D0, ULONG = Number of elements in array
  25. ;* i    cmpfunc, A1, struct Hook * = Hook to be used for comparison.
  26. ;*      The hook will be called with the following arguments: 
  27. ;*       A0 struct Hook* - pointer to the hook itself
  28. ;*       A1 APTR - first pointer in the array for comparison
  29. ;*       A2 APTR - second pointer in the array for comparison
  30. ;* r    success, D0, BOOL = success/failure indicator.
  31. ;* f    This function sorts the given array using an interactive
  32. ;*      quicksort algorythm, no stack problems will occur.
  33. ;*      A buffer will be allocated to hold the
  34. ;*      stack information. If this allocation fails, this function will
  35. ;*      fail. The hook will be used for comparison, and should return
  36. ;*      something like this: 
  37. ;*       <0  e1 <  e2
  38. ;*        0  e1 == e2
  39. ;*       >0  e1 >  e2
  40. ;* e    Hook function for strings:
  41. ;*       LONG __saveds __asm cmpfunc(
  42. ;*        register __a0 struct Hook *hook,
  43. ;*        register __a1 STRPTR e1,
  44. ;*        register __a2 STRPTR e2)
  45. ;*          {
  46. ;*          return strcmp(e1, e2);
  47. ;*          }
  48. ;*****
  49.         XDEF    _QSort
  50. _QSort
  51.  
  52.                 RSRESET
  53. .stack          RS.L    1
  54. .stackpt        RS.L    1
  55. .array          RS.L    1
  56. .elements       RS.L    1
  57. .x              RS.L    1
  58. .hook           RS.L    1
  59. .vars           RS.L    0
  60.  
  61.         pushm.L A3/A6
  62.         lea     (-.vars,SP),SP
  63.  
  64.         move.L  A1,(.hook,SP)
  65.         movem.L A0/D0,(.array,SP)
  66.         movea.L (_SysBase,A4),A6
  67.         asl.L   #3,D0
  68.         moveq   #MEMF_ANY,D1
  69.         call    AllocVec
  70.         tst.L   D0
  71.         beq.S   .nomemerr
  72.         movea.L D0,A3
  73.         move.L  D0,(.stack,SP)
  74.  
  75.         movem.L (.array,SP),A0/D0
  76.         move.L  A0,(A3)+
  77.         add.L   D0,D0
  78.         add.L   D0,D0
  79.         lea     (A0,D0.L),A0
  80.         move.L  A0,(A3)+
  81.  
  82. .lpA    cmpa.L  (.stack,SP),A3
  83.         beq.W   .endsort
  84.         movea.L -(A3),A2
  85.         movea.L -(A3),A1
  86.         subq.L  #4,A2
  87.         move.L  A3,(.stackpt,SP)
  88.  
  89. ; A1 = a
  90. ; A2 = b
  91.  
  92.         move.L  A2,D0
  93.         sub.L   A1,D0
  94.         cmp.L   #2,D0
  95.         blt.S   .lpA    ; nothing to sort
  96.         move.L  (A1),(.x,SP)
  97.  
  98. .lp0    cmpa.L  A1,A2
  99.         bls.S   .ok2
  100.  
  101. .lp1    cmpa.L  A1,A2
  102.         bls.S   .end1
  103.         pushm.L A1-A2
  104.         movea.L (.hook+8,SP),A0
  105.         movea.L (.x+8,SP),A1
  106.         movea.L (A2),A2
  107.         move.L  (h_Entry,A0),A3
  108.         jsr     (A3)
  109.         popm.L  A1-A2
  110.         neg.L   D0
  111.         bmi.S   .end1
  112.         subq.L  #4,A2
  113.         bra.S   .lp1
  114.  
  115. .end1   cmpa.L  A1,A2
  116.         bls.S   .lp2
  117.         move.L  (A2),(A1)++
  118.  
  119. .lp2    cmpa.L  A1,A2
  120.         bls.S   .end2
  121.         pushm.L A1-A2
  122.         movea.L (.hook+8,SP),A0
  123.         movea.L (A1),A1
  124.         movea.L (.x+8,SP),A2
  125.         move.L  (h_Entry,A0),A3
  126.         jsr     (A3)
  127.         popm.L  A1-A2
  128.         neg.L   D0
  129.         bmi.S   .end2
  130.         addq.L  #4,A1
  131.         bra.S   .lp2
  132.  
  133. .end2   cmpa.L  A1,A2
  134.         bls.S   .lp0
  135.         move.L  (A1),(A2)
  136.         subq.L  #4,A2
  137.         bra.S   .lp0
  138.  
  139. .ok2    move.L  (.x,SP),(A1)
  140.  
  141.         movea.L (.stackpt,SP),A3
  142.         addq.L  #4,A3
  143.         move.L  (A3),D0
  144.         move.L  A1,(A3)+
  145.         addq.L  #4,A1
  146.         move.L  A1,(A3)+
  147.         move.L  D0,(A3)+
  148.  
  149.         bra.W   .lpA
  150.  
  151. .endsort
  152.         movea.L (.stack,SP),A1
  153.         call    FreeVec
  154.         moveq   #1,D0
  155. .nomemerr
  156.         lea     (.vars,SP),SP
  157.         popm.L  A3/A6
  158.         rts
  159.  
  160.  
  161.  
  162.  
  163.  
  164.  
  165.  
  166.  
  167.  
  168.